package com.future;

import java.util.PriorityQueue;
import java.util.Stack;

/**
 * Description: 716. 最大栈
 * <p>
 * MaxStack() 初始化栈对象
 * void push(int x) 将元素 x 压入栈中。
 * int pop() 移除栈顶元素并返回这个元素。
 * int top() 返回栈顶元素，无需移除。
 * int peekMax() 检索并返回栈中最大元素，无需移除。
 * int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除 最靠近栈顶 的那个。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/7/19 09:33
 */
public class Solution_716 {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(23);
        stack.add(2);
        stack.add(-12);
        stack.add(90);
        stack.add(5);
        stack.add(5);
        for (int i = stack.size() - 1; i >= 0; i--) {
            if (stack.get(i) == 5) {
                stack.remove(i);
                break;
            }
        }
        System.out.println("==================");
        MaxStack stk = new MaxStack();
        stk.push(5);   // [5] - 5 既是栈顶元素，也是最大元素
        stk.push(1);   // [5, 1] - 栈顶元素是 1，最大元素是 5
        stk.push(5);   // [5, 1, 5] - 5 既是栈顶元素，也是最大元素
        System.out.println(stk.top());     // 返回 5，[5, 1, 5] - 栈没有改变
        System.out.println(stk.popMax());  // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素
        System.out.println(stk.top());     // 返回 1，[5, 1] - 栈没有改变
        System.out.println(stk.peekMax()); // 返回 5，[5, 1] - 栈没有改变
        System.out.println(stk.pop());     // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素
        System.out.println(stk.top());     // 返回 5，[5] - 栈没有改变


    }

}

class MaxStack {

    // 大根堆
    private PriorityQueue<Integer> maxQueue;
    // 栈
    private Stack<Integer> stack;


    public MaxStack() {
        stack = new Stack<>();
        maxQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
    }

    public void push(int x) {
        stack.push(x);
        maxQueue.add(x);
    }

    public int pop() {
        int res = stack.pop();
        maxQueue.remove(res);
        return res;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        int res = maxQueue.peek();
        return res;
    }

    public int popMax() {
        int res = maxQueue.poll();
        // 从栈头遍历，遇到第一个就移除退出
        for (int i = stack.size() - 1; i >= 0; i--) {
            if (stack.get(i) == res) {
                stack.remove(i);
                break;
            }
        }
        return res;
    }

}


